package pers.qianyu.month_202012.date_20201218;

/**
 * 398. 随机数索引
 * https://leetcode-cn.com/problems/random-pick-index/
 *
 * @author mizzle rain
 * @date 2020年12月18日19:48:21
 */
public class RandomNumberIndex {
    // 蓄水池算法
    private int[] nums;

    public RandomNumberIndex(int[] nums) {
        this.nums = nums;
    }

    public int pick(int target) {
        int res = 0;
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            int num = nums[j];
            if (num == target) {
                i++;
                double r = Math.random();
                if (r < 1.0 / i) {
                    res = j;
                }
            }
        }
        return res;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */